#include<iostream>
#include<string>
using namespace std;

void getNextArray(int* next,const string& str);
//str1:模式串 str2:匹配串
int KMP(const string& str1,const string & str2);

void test();

int main() {
    test();
    return 0;
}

void getNextArray(int* next,const string& str)
{
    //初始化
    next[0] = -1;
    next[1] = 0;

    int i=2; //next指针
    int cn = next[i-1]; //前缀末尾
    while(i < str.length()) {
        if(str[i-1] == str[cn]) {
            //公共前后缀长度+1
            next[i++] = cn+1;
            cn = next[i-1];
        } else if(cn > 0){
            //cn向前回溯
            cn = next[cn];
        } else {
            next[i++] = 0;
            cn = next[i-1]; //该语句只是统一理解,此时cn必定为0
        }
    }
}

int KMP(const string& str1,const string & str2)
{
    if(str1.length() > str2.length()) {
        return -1;
    }
    int len = str1.length();
    int* next = new int[len]; //最长公共前后缀数组
    getNextArray(next,str1);
    cout << "the next array of str:" << str1 << endl;
    for(int k=0; k<len; k++) {
        cout << next[k] << " ";
    }
    cout << endl;

    int i = 0, //匹配串指针
        j = 0; //模式串指针
    while(i < str2.length() && j < str1.length()) {
        if(str2[i] == str1[j]) {
            i++;
            j++;
        } else if(next[j] != -1) {
            j = next[j];
        } else {
            i++;
        }
    }
    //释放空间
    if(next) delete next;
    next = nullptr;
    return j>=str1.length() ? i-j : -1;
}

void test()
{
    string str1,str2;
    str1 = "abeabe";
    str2 = "dababecabeabeddd";

    int index = KMP(str1,str2);
    cout << index << endl;
}